#include "node.h"
#include "link.h"
#include <set>
#include <hash_map>
#include <iostream>
#include <queue>
using namespace std;
using namespace AI;
using namespace stdext;
typedef hash_map<int,node*> node_table;
bool hasChildernInSet(node *pnode,set<node*> &nset)
	{
	list<link*> *pll=&pnode->child;
	list<link*>::iterator llitr,llend;
	llend=pll->end();
	for(llitr=pll->begin();llitr!=llend;llitr++)
		{
		list<node*> *pln=&(*llitr)->nodes;
		list<node*>::iterator lnitr,lnend;
		lnend=pln->end();
		for(lnitr=pln->begin();lnitr!=lnend;lnitr++)
			{
			if(nset.find(*lnitr)!=nset.end())
				return true;
			}
		}
	return false;
	}
void AOStarSearch(node& s,node_table &table)
	{
	if(s.isGoal())
		{
		s.solved=true;
		return;
		}
	else
		{
		while(s.solved==false)
			{
			node *cur=&s;
			link *pl=cur->p;
			/* find node to expand.*/
			while(pl!=NULL&&pl->solved!=true)
				{
				list<node*> *node_list=&pl->nodes;
				list<node*>::iterator nlitr,end;
				for(nlitr=node_list->begin();nlitr!=node_list->end();nlitr++)
					{
					if(/*(*nlitr)->p==NULL||*/(*nlitr)->solved==false)break;
					}
				cur=*nlitr;
				pl=cur->p;
				}
			/* now we expand the cur node.*/
			int tmp=cur->getValue()/2;
			int i;
			
			for(i=(tmp-2>0)?tmp-2:1;i<=tmp;i++)
				{
				link *plink=new link(cur);
				node_table::iterator table_itr=table.find(i);
				if(table_itr==table.end())
					{
					node *pnode=new node(i,plink);
					table.insert(pair<int,node*>(i,pnode));
					plink->nodes.push_back(pnode);
					}
				else
					{
					plink->nodes.push_back((*table_itr).second);
					(*table_itr).second->parent.push_back(plink);
					}
				table_itr=table.find(cur->getValue()-i);
				if(table_itr==table.end())
					{
					node *pnode=new node(cur->getValue()-i,plink);
					table.insert(pair<int,node*>(cur->getValue()-i,pnode));
					plink->nodes.push_back(pnode);
					}
				else
					{
					plink->nodes.push_back((*table_itr).second);
					(*table_itr).second->parent.push_back(plink);
					}
				cur->child.push_back(plink);
				}
			/* begin to update h.*/
			typedef set<node*> node_set;
			node_set nset;
			nset.insert(cur);
			while(!nset.empty())
				{
				node_set::iterator nsitr,nend;
				nend=nset.end();
				for(nsitr=nset.begin();nsitr!=nend;nsitr++)
					{
					if(!hasChildernInSet(*nsitr,nset))break;
					}
				cur=*nsitr;
				nset.erase(nsitr);
				/* modify h value.*/
				list<link*> *pll=&cur->child;
				list<link*>::iterator llitr,llend;
				llend=pll->end();
				int minh=INT_MAX;
				link *minlink=NULL;
				bool solved_flag=false;
				for(llitr=pll->begin();llitr!=llend;llitr++)
					{
					int sum=0;
					bool solved=true;
					list<node*> *pln=&(*llitr)->nodes;
					list<node*>::iterator lnitr,lnend;
					lnend=pln->end();
					for(lnitr=pln->begin();lnitr!=lnend;lnitr++)
						{
						sum+=(*lnitr)->h;
						if((*lnitr)->solved==false)
							{
							solved=false;
							}
						}
					sum+=pln->size();
					(*llitr)->h=sum;
					(*llitr)->solved=solved;
					if(sum<minh)
						{
						minh=sum;
						minlink=*llitr;
						}
					/*if((*llitr)->solved==true)
						{
						solved_flag=true;
						}*/
					}
				cur->p=minlink;
				cur->solved=minlink->solved;
				if(minh!=cur->h||cur->solved==true)
					{
					cur->h=minh;
					llend=cur->parent.end();
					for(llitr=cur->parent.begin();llitr!=llend;llitr++)
						{
						nset.insert((*llitr)->parent);
						}
					}
				}
			}
		}
	}
int main()
	{
	int n;
	scanf("%d",&n);
	node s(n,NULL);
	node_table table;
	AOStarSearch(s,table);
	queue<node*> qn;
	qn.push(&s);
	printf("The total cost is %d.\n",s.h);
	while(!qn.empty())
		{
		node *cur=qn.front();
		qn.pop();
		if(cur->isGoal())continue;
		list<node*> *pln=&cur->p->nodes;
		list<node*>::iterator lnitr,lnend;
		lnend=pln->end();
		lnitr=pln->begin();
		printf("%d=%d",cur->getValue(),(*lnitr)->getValue());
		qn.push(*lnitr);
		for(lnitr++;lnitr!=lnend;lnitr++)
			{
			printf("+%d",(*lnitr)->getValue());
			qn.push(*lnitr);
			}
		printf("\n");
		}
	return 0;
	}